/*
 * @lc app=leetcode.cn id=103 lang=cpp
 *
 * [103] 二叉树的锯齿形层次遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

/*
方法二：迭代法
按level order遍历，偶数层时翻转一下（可以用一bool型变量，每一层反号一次）
*/

class Solution
{
 public:
  vector<vector<int>> zigzagLevelOrder(TreeNode* root)
  {
    vector<vector<int>> res;
    if (root == nullptr) return res;

    queue<TreeNode*> q;

    q.push(root);     // 根节点入队
    q.push(nullptr);  // 区分不同层

    vector<int> level;
    bool zigzag = false;  // 标志位决定打印顺序，如果为false则从左到右
    while (q.size())
    {
      TreeNode* t = q.front();
      q.pop();

      if (t)
      {
        level.push_back(t->val);
        if (t->left) q.push(t->left);
        if (t->right) q.push(t->right);
      }
      else
      {
        if (q.size()) q.push(NULL);
        if (zigzag) reverse(level.begin(), level.end());
        zigzag = !zigzag;  // 取反
        res.push_back(level);
        level.clear();
      }
    }
    return res;
  }
};
// @lc code=end
